package com.aqie.medium.dynamicProgram;

/**
 * 647 返回字符串的回文子串
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串 todo
 */
public class CountSubstrings {
    /**
     * 1， 马拉车 O(N) 9ms
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        if(s.length()==0) return 0;
        int mx=0,id=0,count=0;

        StringBuilder sb = new StringBuilder(s);
        for(int i=0;i<=sb.length()-1;i+=2){
            sb.insert(i,"#");
        }
        sb.append("#");
        String str = sb.toString();

        int [] p = new int [str.length()];

        for(int i=0;i<=str.length()-1;i++){

            p[i] = mx>i? Math.min(p[2*id-i],mx-i+1):1;

            while(p[i]+i<=str.length()-1 && i-p[i]>=0){
                if(str.charAt(p[i]+i) == str.charAt(i-p[i])) p[i]++;
                else break;
            }

            if(p[i]+i-1>mx){
                id=i;
                mx=p[i]+i-1;
            }

            count+= p[i]/2;

        }
        return count;
    }

    /**
     * 2, 双指针 4ms
     */
    int num = 0;
    public int countSubstrings2(String s) {
        for (int i=0; i < s.length(); i++){
            count(s, i, i);//回文串长度为奇数
            count(s, i, i+1);//回文串长度为偶数
        }
        return num;
    }

    public void count(String s, int start, int end){
        while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)){
            num++;
            start--;
            end++;
        }
    }

    /**
     * 3, 动态规划
     * @param s
     * @return
     */
    public int countSubstrings3(String s) {
        int cnt = 0;
        int n = s.length();
        char[] charArr = s.toCharArray();
        boolean[][] dp = new boolean[n][n];
        for(int i=n-1;i>=0;i--){//因为要记录dp[i+1][j-1]所以必然要从后向前
            for(int j=i;j<n;j++){
                boolean flag = false;
                flag = ((j-i)<=2)&&charArr[i]==charArr[j];//形如ab，aba
                flag = flag || (charArr[i]==charArr[j] && dp[i+1][j-1]);//形如acdca,a=a，cdc为回文
                if(flag){
                    dp[i][j]=true;
                    cnt++;
                }
            }
        }
        return cnt;
    }

}
